(1) Field of the Invention
The present invention relates to techniques for implementing garbage collection that is suitably applied to real-time processing.
(2) Description of the Related Art
Garbage collection is a type of operating system memory management. The garbage collection is implemented by a garbage collection algorithm to automatically free or deallocate a memory area that is no longer referenced by a program, so that an available memory area is increased. For example, Java™ (a registered trademark of Sun Microsystems, Inc., a cooperation of the United States) is provided with a garbage collector for implementing the algorithm.
The garbage collector deallocates a dynamically allocated memory object (hereinafter, simply referred to as an “object”) to recycle if detecting that the object is no longer referenced. The process to deallocate an object for recycling is also referred to as collecting of an object.
Here, an object means a block of heap area that is dynamically allocated at a request of an application program at run-time. Each object is a variable-length, contiguous block that corresponds to, for example, an object instance in an object-oriented programming language. Each object is composed of (1) at least one set of data paired with its data type, and (2) management information, such as a flag indicating whether the object is valid or not. The data type indicates the type of corresponding data, such as an integer, a logical value, and a pointer. Hereinafter, pointer type data is also referred to simply as a “pointer”.
An object is referenced when another object includes a pointer to the object. That is, when an object A references an object B, the object A includes, as its data content, a pointer to the object B.
All the objects that are referenced at a given time are reachable from one or more root pointers directly or via one or more objects. A route pointer is provided for a part or entire application program depending on the run-time environment such as control mechanism. Therefore, the garbage collector regards objects to be unneeded if they are unreachable from any root pointer at a given time, and collects those unneeded objects.
Hereinafter, description is given briefly to the following conventional garbage collection techniques: mark-and-sweep and reference counting.
The mark-and-sweep system is disclosed, for example, in Publication of Japanese Unexamined Patent Application No. 11-232162. The mark-and-sweep system operates by marking all objects reachable from root pointers, and then scan the entire memory to collect unmarked objects.
The reference counting system operates by keeping, in management information of each object, a count showing how many references there are to that object. The reference count is incremented or decremented each time a reference is modified. An object is collected when a reference count falls to zero.
There are many types of garbage collection other than the techniques mentioned above. None of the conventional techniques, however, is suitably applied to an application program that is required to be highly responsive. This is because a garbage collector needs to interrupt execution of the application program for a long time. In addition, it is extremely difficult to predict when and how long the garbage collector interrupts the application program.
Such a highly-responsive application program is required to complete predetermined processing within a predetermined period of time despite an interruption by a garbage collector.
If the duration of each interruption is sufficiently short comparing with the predetermined time, the application program may be able to complete the predetermined processing timely. In practice, however, a conventional garbage collection operates mainly by processing on the entire memory area, such as tracing of all reachable objects from root pointers through out the memory area, or scanning of the entire memory area to collect unnecessary objects. Consequently, the duration of each interruption is usually long, thereby making it nearly impossible for the application program to complete the required processing within the predetermined time.
Despite such a long duration of an interruption, responsiveness of the application program may still be ensured provided that it is predicted, at the time of designing the application program, when and how long such an interruption will take place. In that case, the application program may be designed to ensure the responsiveness by adjusting time required for each processing constituting the application program. However, it is extremely difficult to predict when and how long an interruption occurs because such prediction can not be made without knowing how much of the memory area is used at different times through the run-time. It is also extremely difficult to predict how much of the memory area is used at a given time because it differs depending on what processing of the application program is executed by that time.